<p>所谓的 PCA(Principal Component Analysis) 就是对数据进行降维。降维好处主要表现在：</p>

<ol>
<li>
减小数据规模，使数据更易于处理
</li>
<li>
减少特征冗余，如果两个特征之间高度线性相关，则留下其中一个即可，用两个就变得多余
</li>
<li>
减少数据噪音
</li>
</ol>

<h2>1. 基本原理</h2>

<p>假设原始输入中每个 data point 都是一个 n 维向量{x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub>}，PCA 实现如下操作。</p>

<p class="center">{x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub>} &rarr; {y<sub>1</sub>, y<sub>2</sub>, ..., y<sub>m</sub>} (m &lt; n)</p>

<p>其中 x 向量和 y 向量可能不在同一空间，其实大多数时候不在一个空间（所谓的不同的空间其实质就是不同的 basis）</p>

<p>那这一过程如何实现。最简单粗暴的降维方式就是直接将输入数据的第 m+1 维到第 n 维去掉，这样就将数据从 n 维降到 m 维，但这样的方式显然不具有普适性，很可能最重要的特征就在第 m+1 维到第 n 维。因此我们需要一种能度量降维合理性的指标（也就是常说的 loss function）。PCA 用的指标就是数据的 variance 最大化，通俗的理解就是保持数据中尽可能多的信息量不丢失。</p>

<p>下面讨论将数据维数降至仅剩 1 维的情况，剩多维的情况类似。</p>

<p>将数据降至一维其实等价于选择某一向量，以下将这一向量记为 v，然后将所有的 data point 都 project 到 v 上，这样问题就变成如何选择 v 使得 project 到其上的数据的 variance 最大。我们可以先从一个通俗的角度考虑这个问题，如果我将数据 project 到 v 后所有数据都被 project 到一个点上，比如所有原始数据都在一条直线上，v 是与该直线垂直的向量，那信息的丢失就大了。显然 project 上去后点越散保持下了的信息量也就越大。也就是说 project 后的数据的 variance 越大越好。</p>

<p>假设原始输入记为随机向量 X = {X<sub>1</sub>, X<sub>2</sub>, ..., X<sub>n</sub>}，其中每一维特征都是一个随机变量，project 后变为 Y（由于只剩一维，所以 Y 是个随机变量，不是随机向量），则 Y = v<sup>T</sup>X。那 project 后的数据的 variance 表示为</p>


<p class="center">$latex Var(Y)=Var(v^{T}X)\\=E((v^{T}X)(v^{T}X)^{T})-E(v^{T}X)E((v^{T}X)^{T})\\=v^{T}E(XX^{T})v-v^{T}E(X)E(X^{T})v\\=v^{T}(E(XX^{T})-E(X)E(X^T))v\\=v^{T}\sum v&bg=ffffff&fg=000000&s=1$</p>

<p>其中&Sigma;为原始输入各维度特征的协方差矩阵。其中 E(v<sup>T</sup>X) = v<sup>T</sup>E(X) 是根据期望的基本性质得到的，即 E(X + Y) = E(X) + E(Y) 和 E(aX) = aE(X)。</p>

<p>那如何最大化 v<sup>T</sup>&Sigma;v 呢？首先注意到如果将 v 的 magnitude 无限放大，那这个表达式的值想多大都可以，最大化也就变得没有意义了，因此我们要限制 v 的 magnitude，在 v 的 magnitude 为某一固定值时，寻找能最大化这一表达式的 v 的方向，这里就令这个 magnitude 为 1，那这一最大化问题可以表示为：</p>

<p class="center">$latex \underset{\left\Vert v \right\Vert = 1}{argmax}\;\; v^T\sum v&bg=ffffff&fg=000000&s=1$</p>

<p>令 $latex L(v)=v^T \sum v - \lambda(\left\Vert v \right\Vert - 1)&bg=ffffff&fg=000000&s=1$，则有</p>

<p class="center">$latex L(v)=v^T \sum v - \lambda(\left\Vert v \right\Vert - 1) \\ \Rightarrow L(v)=v^T \sum v - \lambda(v^Tv - 1) \\ \Rightarrow \frac{\partial L(v)}{\partial v} = 2\sum v - 2\lambda v = 0\\ \Rightarrow \sum v = \lambda v\\ \Rightarrow v^T\sum v = v^T\lambda v = v&bg=ffffff&fg=000000&s=1$</p>

<p>上面的倒数第二个式子告诉我们，能最大化 v<sup>T</sup>&Sigma;v 的 v 必是 &Sigma; 的特征向量，最后一个式子告诉我们这个最大值是 &Sigma; 最大的那个特征值，同时 v 是这个特征值对应的特征向量。</p>

<p>如果要将数据降至多维，可以参考如下我从 <a href="http://math.stackexchange.com/questions/23596/why-is-the-eigenvector-of-a-covariance-matrix-equal-to-a-principal-component">math stackexchange</a> copy 来的答案：</p>

<p class="quote">“If you want to retain more than one dimension of your data set, in principle what you can do is first find the largest principal component, call it u1, then subtract that out from all the data points to get a "flattened" data set that has no variance along u1. Find the principal component of this flattened data set, call it u2. If you stopped here, u1 and u2 would be a basis of the two-dimensional subspace which retains the most variance of the original data; or, you can repeat the process and get as many dimensions as you want. As it turns out, all the vectors u1, u2, … you get from this process are just the eigenvectors of Σ in decreasing order of eigenvalue. That's why these are the principal components of the data set.”</p>

<p>不过在实际中，直接选取最大的 m 个 eigenvalue 对应的 eigenvector 即是。在得到 m 个 eigenvector 后，假设为 V = {V<sub>1</sub>, V<sub>2</sub>, …, V<sub>m</sub>}，原始数据的 data point x (nx1 vector) project 到这 m 个向量上就得到了新的 mx1 的向量 {V<sub>1</sub><sup>T</sup>x, V<sub>2</sub><sup>T</sup>x, …, V<sub>n</sub><sup>T</sup>x} 简写为 V<sup>T</sup>x。</p>

<h2>2. 协方差矩阵构建</h2>

<p>理论上，协方差矩阵 $latex \sum = E[(X-E(X))(X-E(X))^T]&bg=ffffff&fg=000000&s=1&bg=ffffff&fg=000000&s=1$，拆开即：</p>

<p>$latex \sum = \begin{pmatrix} E[(X_1-E(X_1))(X_1-E(X_1))] & E[(X_1-E(X_1))(X_2-E(X_2))] & \cdots & E[(X_1-E(X_1))(X_n-E(X_n))] \\ E[(X_2-E(X_2))(X_1-E(X_1))] & E[(X_2-E(X_2))(X_2-E(X_2))] & \cdots & E[(X_2-E(X_2))(X_n-E(X_n))] \\ \vdots &  \vdots & \ddots & \vdots\\ E[(X_n-E(X_n))(X_1-E(X_1))] & E[(X_n-E(X_n))(X_2-E(X_2))] & \cdots & E[(X_n-E(X_n))(X_n-E(X_n))] \end{pmatrix}&bg=ffffff&fg=000000&s=1$</p>

<p>但实际中，我们无法得到任一特征 X<sub>i</sub> 的真实分布，也就无法计算每个特征的真实期望和方差以及两两特征之间的协方差，因此，我们就用经验(协)方差来代替，即：</p>

<p class="center">$latex {\textstyle \sum_{ii}}=\frac{1}{m}\sum_{k=1}^{m}(X_{ki}-\bar{X_i})^2 \\ \\ {\textstyle \sum_{ij}}=\frac{1}{m}\sum_{k=1}^{m}(X_{ki}-\bar{X_i})(X_{kj}-\bar{X_j})&bg=ffffff&fg=000000&s=1$</p>

<p>其中 m 为训练样本个数，X<sub>ki</sub> 表示第 k 个样本的第 i 维特征，$latex \bar{X_i}=\frac{1}{m}\sum_{k=1}^{m}X_{ki}&bg=ffffff&fg=000000&s=1$。</p>

<p>这里用经验方差还是样本方差都无所谓了，因为前面的常数 1/m 是多少，不影响 PCA 过程。</p>


<h2>P.S. Covariance</h2>

<p>covariance 表示两个随机变量 co-vary 的程度，表针的是他们的线性相关性，且只有它的 sign 是有意义的，正的 covariance 表示两个变量正相关，负的表示负相关， 0 表示不相关。它的 magnitude 与相关程度的强弱无直接关系，能表示相关程度强弱的是 correlation。</p>

<p>任意两个随机变量的 covariance 等于 E((X-E(X))(Y-E(Y)))。</p>

<p>对于包含 n 个特征的输入数据，任意两维特征之间的 covariance 就构成了 covariance matrix。</p>

<h2>P.S. Sample Variance &amp; Empirical Variance</h2>

Sample variance is unbiased estimator of variance, while empirical variance isn't, search google for proof.

